/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：AvlTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-01-16
Function List ：
Description   ：AVL Tree
******************************************************/

#include "AvlTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"
#include "LinkedStack.h"
#include "LinkedQueue.h"

struct AvlNode {
    ElementType Element;
    AvlTree  Left;
    AvlTree  Right;
    int      Height;
};

// Static Function Lists
static int Max(int Lhs, int Rhs);
static int Height(Position P);
static Position SingleRotateWithLeft(Position K2);
static Position SingleRotateWithRight(Position K1);
static Position DoubleRotateWithLeft(Position K3);
static Position DoubleRotateWithRight(Position K1);

AvlTree MakeEmpty(AvlTree T) {
    if (T != NULL) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }

    return NULL;
}

int IsEmpty(AvlTree T) {
    return T == NULL;
}

// Recursive implement
// Position Find(ElementType X, AvlTree T) {
//     if (T == NULL) {
//         return NULL;
//     }

//     if (X < T->Element) {
//         return Find(X, T->Left);
//     } else if (X > T->Element) {
//         return Find(X, T->Right);
//     } else {
//         return T;
//     }
// }

// Non-recursive implement
Position Find(ElementType X, AvlTree T) {
    while (T != NULL) {
        if (X < T->Element) {
            T = T->Left;
        } else if (X > T->Element) {
            T = T->Right;
        } else {
            break;
        }
    }

    return T;
}

// Recursive implement
// Position FindMin(AvlTree T) {
//     if (T == NULL) {
//         return NULL;
//     } else if (T->Left == NULL) {
//         return T;
//     } else {
//         return FindMin(T->Left);
//     }
// }

// Non-recursive implement
Position FindMin(AvlTree T) {
    if (T != NULL) {
        while (T->Left != NULL) {
            T = T->Left;
        }
    }

    return T;
}

// Recursive implement
// Position FindMax(AvlTree T) {
//     if (T == NULL) {
//         return NULL;
//     } else if (T->Right == NULL) {
//         return T;
//     } else {
//         return FindMax(T->Right);
//     }
// }

// Non-recursive implement
Position FindMax(AvlTree T) {
    if (T != NULL) {
        while (T->Right != NULL) {
            T = T->Right;
        }
    }

    return T;
}

static int Max(int Lhs, int Rhs) {
    return Lhs > Rhs ? Lhs : Rhs;
}

static int Height(Position P) {
    if (P == NULL) {
        return -1;
    } else {
        return P->Height;
    }
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position SingleRotateWithLeft(Position K2) {
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    /* Update height */
    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), K2->Height) + 1;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position SingleRotateWithRight(Position K1) {
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    /* Update height */
    K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
    K2->Height = Max(Height(K2->Right), K1->Height) + 1;

    return K2;  /* New root */
}

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithLeft(Position K3) {
    /* Rotate between K1 and K2 */
    K3->Left = SingleRotateWithRight(K3->Left);

    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft(K3);
}

/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithRight(Position K1) {
    /* Rotate between K3 and K2 */
    K1->Right = SingleRotateWithLeft(K1->Right);

    /* Rotate between K1 and K2 */
    return SingleRotateWithRight(K1);
}

AvlTree Insert(ElementType X, AvlTree T) {
    if (T == NULL) {
        /* Create and return a one-node tree */
        T = (AvlTree)malloc(sizeof(struct AvlNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Element = X;
            T->Height = 0;
            T->Left = NULL;
            T->Right = NULL;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2) {
            if (X < T->Left->Element) {
                T = SingleRotateWithLeft(T);
            } else {
                T = DoubleRotateWithLeft(T);
            }
        }
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2) {
            if (X > T->Right->Element) {
                T = SingleRotateWithRight(T);
            } else {
                T = DoubleRotateWithRight(T);
            }
        }
    }
    /* Else X is in the tree already; we'll do nothing */

    /* Update AvlTree height */
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;

    return T;  /* Do not forget this line!! */
}

AvlTree Delete(ElementType X, AvlTree T) {
    Position TmpCell;

    if (T == NULL) {
        Error("Element not found");
    } else if (X < T->Element) {  /* Go left */
        T->Left = Delete(X, T->Left);
        T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
        if (Height(T->Right) - Height(T->Left) == 2) {
            if (Height(T->Right->Right) >= Height(T->Right->Left)) {
                T = SingleRotateWithRight(T);
            } else {
                T = DoubleRotateWithRight(T);
            }
        }
    } else if (X > T->Element) {  /* Go right */
        T->Right = Delete(X, T->Right);
        T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
        if (Height(T->Left) - Height(T->Right) == 2) {
            if (Height(T->Left->Left) >= Height(T->Left->Right)) {
                T = SingleRotateWithLeft(T);
            } else {
                T = DoubleRotateWithLeft(T);
            }
        }
    } else if (T->Left != NULL && T->Right != NULL) {  /* Found element to be deleted Two children */
        /* Replace with smallest in right subtree */
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);

        /* Update height */
        T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
        if (Height(T->Left) - Height(T->Right) == 2) {
            if (Height(T->Left->Left) >= Height(T->Left->Right)) {
                T = SingleRotateWithLeft(T);
            } else {
                T = DoubleRotateWithLeft(T);
            }
        }
    } else {  /* One or zero children */
        TmpCell = T;
        if (T->Left == NULL) {  /* Also handles 0 children */
            T = T->Right;
        } else if (T->Right == NULL) {
            T = T->Left;
        }

        free(TmpCell);
    }

    return T;
}

Position Left(Position P) {
    return P->Left;
}

Position Right(Position P) {
    return P->Right;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// Recursive implement
// void PreorderTraversal(AvlTree T) {
//     if (T != NULL) {
//         printf("%d ", T->Element);
//         PreorderTraversal(T->Left);
//         PreorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void PreorderTraversal(AvlTree T) {
    if (T != NULL) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NULL || !IsEmptyStack(S)) {
            while (P != NULL) {
                printf("%d ", P->Element);
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            P = P->Right;
        }
    }
}

// Recursive implement
// void InorderTraversal(AvlTree T) {
//     if (T != NULL) {
//         InorderTraversal(T->Left);
//         printf("%d ", T->Element);
//         InorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void InorderTraversal(AvlTree T) {
    if (T != NULL) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NULL || !IsEmptyStack(S)) {
            while (P != NULL) {
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            printf("%d ", P->Element);
            P = P->Right;
        }
    }
}

// Recursive implement
// void PostorderTraversal(AvlTree T) {
//     if (T != NULL) {
//         PostorderTraversal(T->Left);
//         PostorderTraversal(T->Right);
//         printf("%d ", T->Element);
//     }
// }

// Non-recursive implement
void PostorderTraversal(AvlTree T) {
    if (T != NULL) {
        LinkedStack S;
        Position Pre;
        Position Cur;

        S = CreateStack();

        Cur = T;
        Pre = NULL;
        while (Cur != NULL || !IsEmptyStack(S)) {
            if (Cur != NULL) {
                Push(Cur, S);
                Cur = Cur->Left;
            } else {
                Cur = Top(S);
                if (Cur->Right != NULL && Cur->Right != Pre) {
                    Cur = Cur->Right;
                } else {
                    Pop(S);
                    printf("%d ", Cur->Element);
                    Pre = Cur;
                    Cur = NULL;
                }
            }
        }
    }
}

void LevelorderTraversal(AvlTree T) {
    if (T != NULL) {
        LinkedQueue Q;

        Q = CreateQueue();

        EnQueue(T, Q);

        while (!IsEmptyQueue(Q)) {
            if (Front(Q)->Left != NULL) {
                EnQueue(Front(Q)->Left, Q);
            }

            if (Front(Q)->Right != NULL) {
                EnQueue(Front(Q)->Right, Q);
            }

            printf("%d ", Retrieve(FrontAndDequeue(Q)));
        }
    }
}

// EOF

